翻訳と辞書 Words near each other ・ Cuthbert W. Pound ・ Cuthbert Whitaker ・ Cuthbert William Johnson ・ Cuthbert Woodroffe ・ Cuthbert, Georgia ・ Cuthbert, Texas ・ Cuthbert-Alphonse Chênevert ・ Cuthberts Building ・ Cuthbertson ・ Cuthbertson High School ・ Cuthbertson Snowfield ・ Cuthburh ・ Cutheard of Lindisfarne ・ Cuthfrith ・ Cuthill ・ Cuthill–McKee algorithm ・ Cuthites ・ Cuthmann of Steyning ・ Cuthona ・ Cuthona abronia ・ Cuthona acinosa ・ Cuthona akibai ・ Cuthona albocrusta ・ Cuthona albopunctata ・ Cuthona amoena ・ Cuthona antarctica ・ Cuthona anulata ・ Cuthona barbadiana ・ Cuthona behrensi ・ Cuthona berghi Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cuthill–McKee algorithm ： ウィキペディア英語版 Cuthill–McKee algorithm In the mathematical subfield of matrix theory, the Cuthill–McKee algorithm (CM), named for Elizabeth Cuthill and J. McKee ,〔E. Cuthill and J. McKee. (the bandwidth of sparse symmetric matrices'' ) In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.〕 is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.〔J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981〕 The Cuthill McKee algorithm is a variant of the standard breadth-first search algorithm used in graph algorithms. It starts with a peripheral node and then generates levels $R\_i$ for $i=1,\; 2,..$ until all nodes are exhausted. The set $R\_$ is created from set $R\_i$ by listing all vertices adjacent to all nodes in $R\_i$. These nodes are listed in increasing degree. This last detail is the only difference with the breadth-first search algorithm. ==Algorithm== Given a symmetric $n\backslash times\; n$ matrix we visualize the matrix as the adjacency matrix of a graph. The Cuthill–McKee algorithm is then a relabeling of the vertices of the graph to reduce the bandwidth of the adjacency matrix. The algorithm produces an ordered ''n''-tuple ''R'' of vertices which is the new order of the vertices. First we choose a peripheral vertex (the vertex with the lowest degree) ''x'' and set ''R'' := (). Then for $i\; =\; 1,2,\backslash dots$ we iterate the following steps while |''R''| < ''n'' *Construct the adjacency set $A\_i$ of $R\_i$ (with $R\_i$ the ''i''-th component of ''R'') and exclude the vertices we already have in ''R'' :$A\_i\; :=\; \backslash operatorname(R\_i)\; \backslash setminus\; R$ *Sort $A\_i$ with ascending vertex order (vertex degree). *Append $A\_i$ to the Result set ''R''. In other words, number the vertices according to a particular breadth-first traversal where neighboring vertices are visited in order from lowest to highest vertex order. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cuthill–McKee algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.